Devices that convert information from one form into another according to a definite procedure are known as automata. One such hypothetical device is the universal Turing machine, which stimulated work leading to the development of modern computers. The Turing machine and its special cases, including finite automata, operate by scanning a data tape, whose striking analogy to information-encoding biopolymers inspired several designs for molecular DNA computers. Laboratory-scale computing using DNA and human-assisted protocols has been demonstrated, but the realization of computing devices operating autonomously on the molecular scale remains rare.
A Turing machine consists of an infinite storage tape divided into tape cells, each of which is capable of storing a single symbol, and a read/write head connecting the tape to a finite control. The machine operates according to a control program, consisting of a finite number of state-transition rules, which are quintuples of the form <S,A,S′,A′,Dir>. Such a rule is interpreted as follows: If the finite control is in state S, and the tape cell of the read/write head contains the symbol A, then change the control state to S′, replace the symbol A by A′, and move the read/write head by one cell in direction Dir (Dir is either “left” or “right”). The Turing machine begins its operation with a finite input written on the otherwise blank tape, the read/write head located on the left-most non-blank symbol, and the control in a designated initial state. The computation progresses according to the control program, and terminates when no State-transition rule applies. The content of the non-blank part of tape upon termination is considered the output of the computation.
In the 1970's, Charles Bennett performed a theoretical investigation of physical computation devices based on the Turing machine model. Bennett was motivated by the observation that the standard electronic computers are inherently energy-inefficient since their basic “store to memory” operation irreversibly erases the content of the memory location. Bennett believed that due to thermodynamic considerations computation devices that proceed in a reversible way would be more efficient, and he proposed two conceptual implementations of the Turing machine model that are reversible. One of these conceptual implementations was called a “Brownian computer” since its operation was based on the Brownian motion of molecules. In Bennett's Brownian computer, named “hypothetical enzymatic Turing machine”, the tape is a macromolecule consisting of a structural backbone bearing tape symbols and a head marker, and each quintuple of the control program is realized by a specific enzyme that effects the transition by removing and adding a tape symbol, and moving the location of the head marker [1]. [Reference: Charles, H. Bennett, The Thermodynamics of Computation—A Review, International Journal of Theoretical Physics, Vol. 21, No. 12, 1982, pp.905-940].
More recently, interest in molecular computation devices resumed following the work of Adelman [15] [Leonard M. Adelman, Molecular computation of solutions to combinatorial problems, Science, 266:1021-1024, 1994] in 1994, which showed how DNA segments combined with DNA related enzymes can be used to effect computations. Adelman's method was based on creating a test-tube solution consisting of DNA segments and performing “biological steps”, effected by a human or a robot, which include adding certain enzymes to the solution, dividing the solution into several tubes, and/or changing the temperature of the solution. At the end of these steps the result of the computation is extracted via standard biological tools.
Following that paper numerous proposals were made on how to implement a DNA-based Turing machine using DNA and related enzymes [see 39]. These proposals fall into two broad classes: one class requires each step of the computation to be effected by a “biological step” as in Adelman's method. The second class [40] creates a set of molecules that “self-assemble” in a way that effects a computation. Also, U.S. Pat. No. 6,266,569, hereby incorporated by reference [29] as if fully set forth herein, describes a molecular Turing machine. However, all of these conceptions of a molecular computing machine focus on Turing machines, rather than finite automata, and also cannot operate completely autonomously.
A finite automaton [26] is a notional computing machine that operates on finite sequences of symbols. The machine can be in one of a finite number of internal states, of which one is designated an initial state and some are designated accepting states. Its software consists of transition rules, each specifying a next state based on the current state and the current symbol. It is initially positioned on the leftmost input symbol in the initial state. In each transition the machine moves one symbol to the right, changing its internal state according to one of the applicable transition rules. Alternatively, it may ‘suspend’ without completing the computation if no transition rule applies. A computation terminates on processing the last input symbol. An automaton is said to accept an input if a computation on this input terminates in an accepting final state.
Another unresolved question for molecular computing is the source of power for the computer. Such a question may be solved in the laboratory by continuously adding an external fuel source. However, if the concept of molecular computing is to eventually become practically applicable to actual computational devices, then the issue of power sources must be resolved.
Simple mathematical computing machines such as finite automata [13, 14] (FIG. 1) scan their input once to produce an output and therefore could destroy the input while scanning without disrupting the computation. One hypothetical way to obtain energy from input destruction, proposed by Bennett [1], is to replace each scanned input symbol by a random symbol. Information destruction by randomization can only extract energy from a non-random input, as randomizing an already random input does not increase entropy [1,2]. Furthermore, it is not clear how this method can be realized in practice. Another approach is to destroy the input structure while preserving the input symbols, effectively turning the sequence of symbols into an unordered collection, the way nucleases digest information-carrying biopolymers while preserving the nucleotides that form them.
Any computation can be accomplished, theoretically, with arbitrarily little energy [1]. Hence if the free energy of the computer's input is higher than that of its output, the computer can, in principle, use the energy difference to accomplish the computation at the expense of input destruction [1, 2]. There is no obvious way to exploit this principle in electronic computers, even in the case of yes/no questions where the output consists of a single bit, and past research on energy-efficient computing focused on reversible computers that avoid information destruction [1-11]. Living systems, in contrast, package information in metastable polymers such as DNA, RNA and proteins [12], the decomposition of which via hydrolysis dissipates heat and increases entropy. This system design inhibits the formation of unwanted random information and facilitates discarding dated, erroneous or hostile information and recycling its constituent bits, rendering the cell an efficient information-processing device.
Currently, the issue of power consumption, power replacement and fuel sources has not been addressed, let alone resolved, for molecular computing machines.